﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0061)http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx -->
<HTML xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<SCRIPT type=text/javascript>
        try { document.domain = "csdn.net"; } catch (ex) { }
    </SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/jquery.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/jquery.highlighter.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/highlighter.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/common.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/AreaCounter.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/feedback.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/relatedarticle.js" 
type=text/javascript></SCRIPT>
<LINK media=all href="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/Cogitation_1.css" 
type=text/css rel=stylesheet><LINK media=all 
href="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/csdn_favbykimi.css" type=text/css 
rel=stylesheet><LINK href="http://profile.csdn.net/Solstice/picture/1.ico" 
rel="Shortcut Icon"><LINK title=RSS 
href="http://feeds.feedsky.com/csdn.net/Solstice" type=application/rss+xml 
rel=alternate>
<META content="MSHTML 6.00.2900.5897" name=GENERATOR></HEAD>
<BODY id=defaultuser>
<DIV id=csdnblog_allwrap>
<DIV id=csdnblog_midwrap>
<DIV id=csdnblog_header>
<H1><A href="http://blog.csdn.net/Solstice">陈硕的Blog</A></H1>
<H2>吾尝终日而思矣，不如须臾之所学也。吾尝跂而望矣，不如登高之博见也。……君子生非异也，善假于物也。</H2>
<UL id=personalnav>
  <LI style="DISPLAY: none"><A id=a_login 
  href="http://passport.csdn.net/UserLogin.aspx">登录</A> </LI>
  <LI style="DISPLAY: none"><A id=a_register 
  href="http://passport.csdn.net/CSDNUserRegister.aspx" target=_blank>注册</A> 
  </LI>
  <LI style="DISPLAY: none"><A id=a_welcome href="http://hi.csdn.net/" 
  target=_blank>欢迎</A> </LI>
  <LI style="DISPLAY: none"><A id=a_exit 
  href="http://writeblog.csdn.net/Signout.aspx">退出</A> </LI>
  <LI style="DISPLAY: none"><A id=a_myblog href="http://blog.csdn.net/">我的博客</A> 
  </LI>
  <LI style="DISPLAY: none"><A id=a_configure 
  href="http://writeblog.csdn.net/configure.aspx" target=_blank>配置</A> </LI>
  <LI style="DISPLAY: none"><A id=a_postedit 
  href="http://writeblog.csdn.net/PostEdit.aspx" target=_blank>写文章</A> </LI>
  <LI style="DISPLAY: none"><A id=a_postlist 
  href="http://writeblog.csdn.net/PostList.aspx" target=_blank>文章管理</A> </LI>
  <LI style="DISPLAY: none"><A id=a_bloghome href="http://blog.csdn.net/" 
  target=_blank>博客首页</A> </LI></UL>
<UL id=blogsearchsty>
  <LI><INPUT class=bolgsearch id=inputSearch> </LI>
  <LI class=selectsty><SELECT id=Search_ddlSearchScope 
  name=Search:ddlSearchScope> <OPTION value=all selected>全站</OPTION> <OPTION 
    value=Solstice>当前博客</OPTION></SELECT> </LI>
  <LI><INPUT class=bolggobtn id=buttonSearch type=button value=搜索> </LI></UL>
<UL id=menu>
  <LI><A href="http://hi.csdn.net/Solstice" target=_blank>空间</A> </LI>
  <LI><A class=on href="http://blog.csdn.net/Solstice">博客</A> </LI>
  <LI><A href="http://hi.csdn.net/!s/friend/list/Solstice" target=_blank>好友</A> 
  </LI>
  <LI><A href="http://hi.csdn.net/!s/album/list/Solstice" target=_blank>相册</A> 
  </LI>
  <LI><A class=last href="http://hi.csdn.net/!s/wall/to/Solstice" 
  target=_blank>留言</A> </LI></UL></DIV>
<SCRIPT type=text/javascript>
	var CurrentUserName = 'Solstice';
</SCRIPT>

<DIV id=csdnblog_sidebar>
<DIV class=gutter>
<DIV class=aboutauthor>
<DL>
  <DT>用户操作 
  <DD class=middle><A href="http://hi.csdn.net/!s/wall/to/Solstice" 
  target=_blank>[留言]</A>&nbsp; <A href="http://hi.csdn.net/!s/msg/to/Solstice" 
  target=_blank>[发消息]</A>&nbsp; <A 
  href="http://hi.csdn.net/!s/friend/add/Solstice" 
  target=_blank>[加为好友]</A>&nbsp; <SPAN id=userInfo></SPAN><SPAN 
  id=SubscriptionList>
  <DT>订阅我的博客 
  <DD><A href="http://feeds.feedsky.com/csdn.net/Solstice"><IMG alt=XML聚合 
  src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/gif.gif" border=0> </A>&nbsp;&nbsp; 
  <A href="http://feeds.feedsky.com/csdn.net/Solstice" target=_blank><IMG 
  alt=FeedSky src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/feedsky.gif" border=0> 
  </A>
  <DD><A 
  href="http://www.xianguo.com/subscribe.php?url=http://feeds.feedsky.com/csdn.net/Solstice" 
  target=_blank><IMG alt=订阅到鲜果 
  src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss_xianguo.jpg" border=0> </A>
  <DD><A 
  href="http://fusion.google.com/add?feedurl=http://feeds.feedsky.com/csdn.net/Solstice" 
  target=_blank><IMG alt=订阅到Google 
  src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss_google.gif" border=0> </A>
  <DD><A 
  href="http://www.zhuaxia.com/add_channel.php?url=http://feeds.feedsky.com/csdn.net/Solstice" 
  target=_blank><IMG alt=订阅到抓虾 
  src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss_zhuaxia.gif" border=0> 
  </A></SPAN>
  <DT><SPAN class=floatright style="DISPLAY: none"><A class=a_edit 
  href="http://writeblog.csdn.net/configure.aspx" 
  target=_blank>[编辑]</A></SPAN>Solstice的公告 
  <DD>
  <DT><SPAN class=floatright style="DISPLAY: none"><A class=a_edit 
  href="http://writeblog.csdn.net/EditCategories.aspx?catID=1" 
  target=_blank>[编辑]</A></SPAN>文章分类 
  <DD>
  <DIV class=publiclist_sidebar>
  <UL>
    <LI><A href="http://blog.csdn.net/Solstice/category/9111.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    href="http://blog.csdn.net/Solstice/category/9111.aspx">c++</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/166369.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    title="《Code Complete 中文版 第二版》的统稿流水帐。" 
    href="http://blog.csdn.net/Solstice/category/166369.aspx">Code Complete 2nd 
    ed.</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/71.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    title="Some debugging tricks that I use everyday." 
    href="http://blog.csdn.net/Solstice/category/71.aspx">Debugging without 
    debugger</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/153521.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    href="http://blog.csdn.net/Solstice/category/153521.aspx">Digital Circuit 
    Design with Verilog</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/21244.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    title="一套把C++扩展为硬件描述语言的Class Library." 
    href="http://blog.csdn.net/Solstice/category/21244.aspx">SystemC</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/70.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    title=个人排版经验与技巧。 
    href="http://blog.csdn.net/Solstice/category/70.aspx">Typesetting with LaTeX 
    &amp; Word</A>
    <LI><A href="http://blog.csdn.net/Solstice/category/74.aspx/rss"><IMG 
    alt=(RSS) src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rss.gif"></A><A 
    title=Misc. 
  href="http://blog.csdn.net/Solstice/category/74.aspx">杂感</A></LI></UL></DIV>
  <DT>存档 
  <DD>
  <DIV class=publiclist_sidebar>
  <UL>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2009/08.aspx">2009年08月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2009/04.aspx">2009年04月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2009/01.aspx">2009年01月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2008/11.aspx">2008年11月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2008/10.aspx">2008年10月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2008/07.aspx">2008年07月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2008/05.aspx">2008年05月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2008/02.aspx">2008年02月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2007/10.aspx">2007年10月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2007/04.aspx">2007年04月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2007/03.aspx">2007年03月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/12.aspx">2006年12月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/09.aspx">2006年09月(2)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/08.aspx">2006年08月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/04.aspx">2006年04月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/03.aspx">2006年03月(4)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/02.aspx">2006年02月(5)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2006/01.aspx">2006年01月(3)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2005/12.aspx">2005年12月(7)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2005/11.aspx">2005年11月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2005/10.aspx">2005年10月(2)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2005/09.aspx">2005年09月(3)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2004/11.aspx">2004年11月(5)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2004/07.aspx">2004年07月(2)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2004/06.aspx">2004年06月(2)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2004/05.aspx">2004年05月(4)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2004/04.aspx">2004年04月(6)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2003/08.aspx">2003年08月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2003/04.aspx">2003年04月(3)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2002/10.aspx">2002年10月(1)</A>
    <LI><A 
    href="http://blog.csdn.net/Solstice/archive/2001/10.aspx">2001年10月(1)</A></LI></UL></DIV></DD></DL></DIV></DIV></DIV>
<DIV id=csdnblog_content>
<DIV class=gutter>
<DIV class=default_contents>
<DIV class=user_article>
<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/feedbackcount.js" 
type=text/javascript></SCRIPT>

<H1 class=title_txt><IMG height=16 alt=原创 
src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/authorship.gif" width=15 
border=0>&nbsp; 谈谈数独(Sudoku) <CITE class=fav_csdnstylebykimi><A 
class=fav_csdnstylebykimi title=收藏到我的网摘中，并分享给我的朋友 
href="javascript:d=document;t=d.selection?(d.selection.type!='None'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():'');void(saveit=window.open('http://wz.csdn.net/storeit.aspx?t='+escape(d.title)+'&amp;u='+escape(d.location.href)+'&amp;c='+escape(t),'saveit','scrollbars=no,width=590,height=300,left=75,top=20,status=no,resizable=yes'));saveit.focus();">收藏</A> 
</CITE></H1>
<DIV class=blogstory>
<SCRIPT type=text/javascript>
                        document.body.oncopy = function() {
                            if (window.clipboardData) {
                                setTimeout(function() {
                                    var text = clipboardData.getData("text");
                                    if (text && text.length > 300) {
                                        text = text + "\r\n\n本文来自CSDN博客，转载请标明出处：" + location.href;
                                        clipboardData.setData("text", text);
                                    }
                                }, 100);
                            }
                        }
					</SCRIPT>

<SCRIPT type=text/javascript>                        function StorePage() { d = document; t = d.selection ? (d.selection.type != 'None' ? d.selection.createRange().text : '') : (d.getSelection ? d.getSelection() : ''); void (keyit = window.open('http://www.365key.com/storeit.aspx?t=' + escape(d.title) + '&u=' + escape(d.location.href) + '&c=' + escape(t), 'keyit', 'scrollbars=no,width=475,height=575,left=75,top=20,status=no,resizable=yes')); keyit.focus(); }</SCRIPT>

<H1>谈谈 Sudoku 
(数独)</H1><BR>除特别说明外，本文提到的Sudoku是指9x9的经典Sudoku。本文大量参考了维基百科的相关条目。<BR><BR>
<H1>Sudoku 介绍</H1><BR>Sudoku 
是一种数学游戏，把一个9行9列的棋盘分为9个3x3的方块，在棋盘上填入1~9这九个数字，使得每行(row)每列(column)每块(block)的9个格子内数字不重复。<BR><BR>例如下面是一个填好的Sudoku。<BR><BR><SPAN 
style="FONT-FAMILY: Courier New">123|456|789</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">456|789|123</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">789|123|456</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">---+---+---</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">231|564|897</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">564|897|231</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">897|231|564</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">---+---+---</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">312|645|978</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">645|978|312</SPAN><BR 
style="FONT-FAMILY: Courier New"><SPAN 
style="FONT-FAMILY: Courier New">978|312|645</SPAN><BR><BR>用n个符号（通常是1~n的整数）排成n行n列的方阵，如果每一行和每一列都没有重复的符号，就称为一个n阶拉丁方（http: 
//baike.baidu.com/view/1128476.htm）。Sudoku 
是特殊的9阶拉丁方。9阶拉丁方约有5.52E+27种可能，而Sudoku增加了“block内数字不重复”这一约束，其数目要远少于此。<BR><BR>Sudoku 
游戏通常会给一些提示（约束），在某些格子上事先填好数字，然后让游戏者填完其余的格子。如果一个提示都没有，任由游戏者发挥，那么一共有大约6.67E+21种不同的答案（http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf）。<BR><BR>虽然没有严格的证明，但似乎至少要有17个提示（事先填好17个数）才能确保答案是唯一的。有人列出了四万多个这种17-hint的Sudoku题目（http://people.csse.uwa.edu.au/gordon/sudokumin.php）。<BR>另外借助通过计算机搜索，目前还没有找到只要16个提示就能保证答案唯一的Sudoku题目（http://www.math.ie/checker.html）。<BR><BR>一个 
Sudoku 问题可以通过以下变换转换为等价的Sudoku问题：<BR>
<OL>
  <LI>数字排列，例如1换为2，2换为4，4换为1等等。共有9! = 362880种排列方式。 
  <LI>排列同一块中的行，例如第1行与第2行互换，第4行与第6行互换。（但第3行不能与第4行互换。）每块有3!=6种行排列方式，而且块内的行排列是独立的，与其他块无关，因此共有6^3=216种。 

  <LI>排列同一块中的列，例如第1列与第3列互换等等。每块有3!=6种列排列方式，而且块内的列排列是独立的，与其他块无关，因此共有6^3=216种。 
  <LI>整块的行排列，例如第1~3行整体与4~6行互换。一共有3!=6种排列方式。 
  <LI>整块的列排列，例如第1~3列整体与7~9列互换。一共有3!=6种排列方式。 
  <LI>转置（行列互换），有2种可能。 </LI></OL>这并不意味着每个Sudoku问题可变出9! x 6^8 x 
2个等价问题。因为某些变换不一定能产生新的问题，而某些变换会产生重复的新问题。例如考虑只有对角线上有数字的Sudoku问题，那么转置就不能变出新 
问题；再考虑只有第一行有数字的sudoku问题，用第3、5变换产生的新问题都能由第1变换得到。<BR><BR>
<H1>Sudoku 程序求解<BR></H1>
<H2>回溯算法</H2>Sudoku 
问题很像八皇后问题，都可以用回溯算法解决。一个Sudoku问题可以表示为一个棋盘，已经填了一些数，余下n个空格待填。思路是：如果n==0，说明填 
满了，程序结束。否则找到一个空格，试着填一个数（依次从1~9中选），然后看能不能求解这个子问题（原问题是填n个空格，子问题是填n-1个空格），如 
果子问题不能求解（求解子问题这一步通常用递归），就试着填下一个数 
（例如第一次试着填1，第二次试试2），如果试到9都不能满足，说明当前问题无解。这个算法是相当直接的，对付大多数问题也能迅速解决。有一处明显的改 
进：在找待填空格时选择可用数字最少的空格，也就是说选择可能数目最少的分支，这样能大大减少试探的次数。以下是程序所用的数据结构，全部为数组，基本用 
C语言实现：<BR><BR>// 基本数据：<BR>const int N = 81; // 棋盘上有9x9=81个格子<BR>const int 
NEIGHBOR = 20; // 每个格子有20个相邻的格子（同一行，同一列，同一块）<BR>int board[N]; // 
棋盘，值表示所填的数字<BR>int neighbors[N][NEIGHBOR]; // 邻居数组，值表示在棋盘中的下标，例如 neighbors[2][3] 
表示第2个格子的第3个邻居的下标。<BR>int spaces[N]; // 待填的空格，至多N个，值表示在棋盘中的下标<BR>int nspaces; // 
棋盘上最初的空格总数<BR><BR>// 
以上数据已经足够写出回溯程序（甚至不用neighbors数组也行），不过为了加快运行速度，我使用了以下补充数据，用作cache<BR>int 
arities[N]; // 格子的“自由度”，arities[x]表示x这个格子目前的候选数字的个数，选待填格子时应选arity最小的格子。<BR>bool 
available[N][10]; // 
格子有哪些数字可用，例如available[3][2]==true说明第3号格子能填入数字2。<BR><BR>在回溯过程中，会频繁更新board、arities、available等数组。而neighbors数组的内容在程序运行中不会变化。在判断能否填数 
时，不用检查board中的多个相邻元素，只需访问一次available就行，这是以空间换时间的做法。用这种方法写的程序求解一个Sudoku问题的 
用时大约在毫秒级别。<BR><BR>
<H2>精确覆盖算法（Exact Cover）</H2><BR>另一种求解Sudoku的办法是把它转换为 <A id=oo8f 
title="Exact Cover" href="http://en.wikipedia.org/wiki/Exact_cover">Exact 
Cover</A> 问题。Exact Cover问题是指对于一个稀疏的0/1矩阵，选出一些行，使得由这些行构成的新矩阵中每一列有且仅有一个1。（注：Exact 
Cover是NPC问题，一般化的Sudoku（棋盘大小不限于9x9，而是n^2 x n^2，分为n x n块）也是NPC问题。）<BR><BR>Knuth 
描述了用于解决 Exact Cover 问题的<A id=y1x. title="Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Algorithm X</A> 
（一个递归的、非确定的、深度优先蛮力搜索算法），并给出了一个巧妙利用指针和双向链表的高效实现技术，称为<A id=geu- 
title="Dancing Links" 
href="http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz">Dancing 
Links</A>。 (ps: 
http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz , pdf: 
http://lanl.arxiv.org/PS_cache/cs/pdf/0011/0011047v1.pdf) <BR><BR>Knuth 自己还写了 
Dancing Links 程序(http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w)和 
Sudoku 
求解程序(http://www-cs-faculty.stanford.edu/~knuth/programs/sudoku.w)。这个程序不仅能求解Sudoku，还能枚举出所有满足条件的解法。<BR><BR>Apache的Hadoop项目是开源的Java语言MapReduce实现，它附带的示例中有使用Dancing 
Links技术的Sudoku求解程序(http: 
//svn.apache.org/viewvc/hadoop/core/trunk/src/examples/org/apache/hadoop/examples/dancing/)。 
由于Sudoku问题的规模比较小，求解一个问题的用时通常少于一秒钟，所以这个程序其实没有用到分布式计算。<BR><BR><BR>Sudoku 
是个很有意思的问题，不难解决，而且有很多好玩的地方。<BR><BR><BR><BR>&nbsp; 
<P class="right articalinfo">发表于 @ 2008年02月15日　00:15:00&nbsp;| <A id=a_comment 
title=评论 
href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#FeedBack">评论( 
<SPAN id=FeedbackCount_2096209>loading...</SPAN>
<SCRIPT type=text/javascript>
                                AddFeedbackCountStack("2096209")
							</SCRIPT>
 ) </A>| <SPAN style="DISPLAY: none"><A class=a_edit title=编辑 
href="http://writeblog.csdn.net/PostEdit.aspx?entryId=2096209">编辑</A>|</SPAN> <A 
href="mailto:webmaster@csdn.net?subject=Article Report!!!&amp;body=Author:SolsticeURL:http://blog.csdn.net/ArticleContent.aspx?UserName=Solstice&amp;Entryid=2096209">举报</A>| 
<CITE class=fav_csdnstylebykimi><A class=fav_csdnstylebykimi 
title=收藏到我的网摘中，并分享给我的朋友 
href="javascript:d=document;t=d.selection?(d.selection.type!='None'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():'');void(saveit=window.open('http://wz.csdn.net/storeit.aspx?t='+escape(d.title)+'&amp;u='+escape(d.location.href)+'&amp;c='+escape(t),'saveit','scrollbars=no,width=590,height=300,left=75,top=20,status=no,resizable=yes'));saveit.focus();">收藏</A> 
</CITE></P><SPAN id=Post.ascx_ViewPost_PreviousAndNextEntriesDown>
<H3 class=pagego><A 
href="http://blog.csdn.net/Solstice/archive/2007/10/27/1847728.aspx">旧一篇:为perforce添加nothave命令，查找尚未添加到depot中的文件（in 
Ruby）</A>&nbsp;|&nbsp;<A 
href="http://blog.csdn.net/Solstice/archive/2008/05/13/2439309.aspx">新一篇:为 bash 
添加 auto_cd 功能：如果命令行是一个目录，则进入该目录</A></H3></SPAN>
<DIV class=mutualitys>
<DL>
  <DT>相关文章<SPAN><A onclick=LogClickCount(this,183) 
  href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#" 
  target=_blank></A></SPAN> </DT></DL></DIV></DIV></DIV><A name=FeedBack></A>
<SCRIPT type=text/javascript>
                var CurrentEntryId = '2096209';
            </SCRIPT>

<DIV class=commentslist id=commentslist></DIV>
<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/CsdnDialog.js" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>
                function ChangeIdentifyingCode() {
                    var url = $('#imgValidationCode').attr('src');
                    if (!(/&d=[\d\.]+$/).test(url)) url += "&d=1";
                    url = url.replace(/&d=[\d\.]+$/, "&d=" + Math.random());
                    $('#imgValidationCode').attr('src', url);
                }

                function OpenLoginDialog() {
                    element = document.getElementById("loginBtn");
                    var position = absolutePoint(element);
                    
                    var dialogTop = position.y - 400;
                    var dialogLeft = position.x - 220;
                    var dialogWidth = 435;
                    var dialogHeight = 420;
                    
                    showWindow({ url: 'http://passport.csdn.net/UserLogin.aspx?show=replyLogin&from=http%3a%2f%2fblog.csdn.net%2f!tools%2fLoginSussess.aspx'
                        , title: '登录'
                        , top: dialogTop
                        , left: dialogLeft
                        , width: dialogWidth
                        , height: dialogHeight
                    });
                }
                
                function closeDialog(needRefresh) {
                    closeWindow();
                    if (needRefresh) {
                        var url = location.href;
                        if ((/\?/g).test(url))
                            url = url.replace(/\?.*$/g, ("?" + Math.random()).replace(/\./g, ""));
                        else url += ("?" + Math.random()).replace(/\./g, "");
                        location.href = url;
                    }
                    $("#SubmitFeedback").unbind("click");
                    $("#SubmitFeedback").bind("click", PostContent);
                }
                
                function absolutePoint(element) {
                    var result = { x: element.offsetLeft, y: element.offsetTop };
                    element = element.offsetParent;
                    while (element) {
                        result.x += element.offsetLeft;
                        result.y += element.offsetTop;
                        element = element.offsetParent;
                    }
                    return result;
                }
            </SCRIPT>

<DIV class=commentnew>
<DL>
  <DT>
  <UL>
    <LI class=left>发表评论
    <SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/rsscache.aspx" 
    type=text/javascript></SCRIPT>
     </LI></UL></DT>
  <DD>
  <UL>
    <LI class=lefttop>表 情： </LI>
    <LI class=right><A onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=顶 alt=顶 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e01.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=砸 alt=砸 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e02.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=棒 alt=棒 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e03.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=大笑 alt=大笑 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e04.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=愤怒 alt=愤怒 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e05.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=大哭 alt=大哭 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e06.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=疑问 alt=疑问 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e07.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=汗 alt=汗 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e08.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=呕吐 alt=呕吐 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e09.gif"></A> <A 
    onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=brow title=送花 alt=送花 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/e10.gif"></A> </LI></UL>
  <UL>
    <LI class=left>评论内容： </LI>
    <LI class=right><TEXTAREA class=textarea id=content></TEXTAREA> </LI></UL>
  <DIV>
  <UL>
    <LI class=left>用 户 名： </LI>
    <LI class=right><SPAN class=right id=loginTips style="DISPLAY: none"><A 
    class=red id=loginBtn onclick="OpenLoginDialog(this);return false;" 
    href="javascript:void(0);">登录</A> <A class=red 
    href="http://passport.csdn.net/CSDNUserRegister.aspx" target=_blank>注册</A> 
    </SPAN><SPAN class=right style="DISPLAY: none"><INPUT class=checkbox 
    id=anonymous type=checkbox>匿名评论 </SPAN><SPAN class=left 
    id=commentUser></SPAN></LI></UL></DIV>
  <UL style="DISPLAY: none">
    <LI class=left>验 证 码： </LI>
    <LI class=right><INPUT class=input id=code> <A 
    href="javascript:ChangeIdentifyingCode()"><IMG id=imgValidationCode 
    style="VERTICAL-ALIGN: middle" alt=验证码 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/AntiBotImage.htm"></A> <A 
    href="javascript:ChangeIdentifyingCode()">重新获得验证码</A> </LI></UL>
  <UL>
    <LI class=left> </LI>
    <LI class=right><A onclick="return false;" 
    href="http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx#"><IMG 
    class=btn id=SubmitFeedback style="VERTICAL-ALIGN: middle" 
    src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/comment_btn.gif"></A> 
  </LI></UL></DD></DL></DIV>
<SCRIPT type=text/javascript>
                LoadFeedbackCount();
                document.write("<img src='http://counter.csdn.net/pv.aspx?id=24' border=0 width=0 height=0>");
			</SCRIPT>
</DIV></DIV></DIV>
<DIV id=pubfooter>
<DL>
  <DT>
  <DD>Copyright © Solstice 
  <DD>Powered by CSDN Blog </DD></DL></DIV>
<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/counter.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/ga.js" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>
    try {
        var pageTracker = _gat._getTracker("UA-2688088-9");
        pageTracker._trackPageview();
    } catch (err) { }
</SCRIPT>
</DIV></DIV><IMG height=0 src="谈谈数独(Sudoku) - 陈硕的Blog - CSDN博客.files/count.htm" 
width=0> </BODY></HTML>
